COMMENT ⊗   VALID 00004 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.require "lsp.pub[1,clt]" source_file
C00003 00003	.s IMPURE PROGRAMS AND UNCLEAN PROGRAMS
C00009 00004	.skip to column 1
C00010 ENDMK
C⊗;
.require "lsp.pub[1,clt]" source_file;
.PORTION MAINPORTION
.sname ← SSNAME ← NULL
.NEXT SECTION  
.NEXT SECTION
.NEXT SECTION

.s IMPURE PROGRAMS AND UNCLEAN PROGRAMS


	Pure clean LISP programs admit the elegant mathematical
characterization described and applied in Chapter 3.
Specifically, each recursively defined pure clean LISP function
can be translated into a functional equation and minimization
schema in a first order language, and the function and schema
can be used to prove that the program meets its extensional
specifications.

	In this chapter we shall describe some additional features of
practical LISP systems for which good mathematical characterizations
have not yet been found.  Every computation that can be done with
these features can be done in pure clean LISP, but nevertheless there
are good reasons for sometimes using these features.  We shall examine
the features themselves and also the criteria that determine when
they should be used in preference to pure clean LISP.


.ss "Sequential (Algol-like) programs."

	Sequential programs are impure, but can be clean provided
certain restrictions are observed.  The external notation for
sequential programs is adapted from that of Algol 60.  We allow
as a term an expression of the form

	%2program[<variable list>,<statement list>]%1,

where %2<variable list>%1 is a list of variables local to the
program, and %2<statement list>%1 is a list of the statements of
the program.  As in Algol 60, the statements are separated by
semicolons, and any statement may be preceded by a label followed
by a colon.

	The statements are of the following kinds:

	1. Assignment statements of the form

	%2<left hand side> ← <right hand side>%1,

where %2<left hand side>%1 is a variable, possibly subscripted, and
%2<right hand side>%1 is a LISP expression that can be evaluated.

	2. %3go to%1 statements of the form

	%3go to%2 a%1

where %2a%1 is a label or a conditional expression that evaluates to a
label.

	3. A conditional statement which has the form

	%2qif p1 qthen s1 qelse qif ... qelse qif pn qelse sn%1,

where the %2p%1's are propositional expressions having truth values,
and the %2s%1's are any statements.

	4. %3return%2 e%1

where %2e%1 is an arbitrary expression.  The effect of executing this
expression is to return from the program giving the program the value
of the expression %2e%1.

	As an example, we might write %2reverse%1 as follows:

.nofill

	%2reverse u ← %3program%2[[v];
		v ← qNIL;
	a:	qif qn u qthen %3return%2 v;
		v ← qa u . v;
		u ← qd v;
		%3go to%1 a]%1.
.fill

	The internal form of the same program is

.nofill

	(DE REVERSE (U) (PROG (V)
		(SETQ V NIL)
		A
		(COND ((NULL U) (RETURN V)))
		(SETQ V (CONS (CAR U) V))
		(SETQ U (CDR U))
		(GO A)
	))
.fill

where the paragraphing is only for the reader's convenience.  Notice that
in internal form, labels are statements rather than attachments to
statements.

	Here are some ways we might write %2append%1:
.nofill

	%2u * v ← %3program%2[
		%3return%2 qif qn u qthen v qelse qa u . [qd u * v]]%1,

.fill
is just a trivial rewrite of the recursive definition.
.nofill

	%2u * v ← qprogram[w;
		qif qn u qthen qreturn v;
		w ← qa u . [qd u * v];
		qreturn w]%1

.fill
is almost as close to the pure LISP form.  If we want to replace the
recursion by a loop, we can write

.nofill
	%2u * v ← qprogram[w;
		w ← qNIL;
	a:	qif qn u qthen qgoto b;
		w ← qa u . w;
		u ← qd u;
		qgoto a;
	b:	qif qn w qthen qreturn v;
		v ← qa w . v;
		qw ← qd w;
		qgoto b]%1.

.fill
This corresponds to the recursive program
.nofill

	%2u * v ← app[u,v,qnil]

	app[u,v,w] ← qif qn u qthen [qif qn w qthen v qelse app[u,qa w . v,qd w]]
		qelse app[qd u,v,qa u . w]%1

.fill
which can save some storage if it is compiled or interpreted without
using the stack.
.skip to column 1
1. Sequential programs

2. Side effects

3. Property lists

4. Input and output